// https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
 var buildTree = function(preorder, inorder) {
  // ternimator
  if (!preorder.length) {
      return null;
  }
  const root = preorder[0];
  const leftPreorder = preorder.slice(1, 1 + inorder.indexOf(root));
  const leftInorder = inorder.slice(0, leftPreorder.length);
  const rightPreorder = preorder.slice(1 + inorder.indexOf(root));
  const rightInorder = inorder.slice(leftPreorder.length + 1);
  // process & drill down
  return new TreeNode(root, buildTree(leftPreorder, leftInorder), buildTree(rightPreorder, rightInorder));
};
